package com.mimi.datastruct.leetcode;

import com.sun.xml.internal.ws.util.xml.CDATA;
import org.junit.Test;
import org.omg.CORBA.INTERNAL;
import sun.nio.cs.ext.MacHebrew;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * @ClassName test
 * @Description 498982703@qq.com
 * @Author gary
 * @Date 2020/12/1 10:07
 * @Version 1.0
 */
public class test {

    @Test
    public void test1() {
        String[] words = new String[]{"abc", "bbc", "ccc"};
        String s = "ab";
        String s1 = boldWords(words, s);
        System.out.println(s1);

    }

    @Test
    public void testSum() {
        String[] words = new String[]{"abc", "bbc", "ccc"};
        String s = "ab";
        String s1 = boldWords(words, s);
        System.out.println(s1);

    }

    @Test
    public void test2() {
        int[] arry = {1,0,0,0,1};
        int target = 1;
        System.out.println(canPlaceFlowers(arry, target));

    }
    @Test
    public void test3() {
        String str = "babad";
        System.out.println(longesPalinedrome(str));


    }

    public String longesPalinedrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {
                    dp[i][j] = true;
                } else if (l == 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && l + 1 > ans.length()) {
                    ans = s.substring(i, i + l + 1);
                }
            }
        }
        return ans;
    }

    /**
     *
     * @param s
     * @return
     */
    public String decodeString(String s) {
        StringBuilder res = new StringBuilder();
        int multi = 0;
        LinkedList<Integer> stack_multi = new LinkedList<>();
        LinkedList<String> stack_res = new LinkedList<>();
        for (Character c : s.toCharArray()) {
            if (c == '[') {
                stack_multi.addLast(multi);
                stack_res.addLast(res.toString());
                multi = 0;
                res = new StringBuilder();
            } else if (c == ']') {
                StringBuilder tmp = new StringBuilder();
                int cur_multi = stack_multi.removeLast();
                for (int i = 0; i < cur_multi; i++) {
                    tmp.append(res);
                }
                res = new StringBuilder(stack_res.removeLast() + tmp);
            } else if (c>='0'&&c<='9') {
                multi = multi * 10 + Integer.parseInt(c + "");
            }else {
                res.append(c);
            }
        }
        return res.toString();

    }

    /**
     * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
//        System.arraycopy(nums2, 0, nums1, m, n);
//        Arrays.sort(nums1);
        int[] temp = new int[m + n];
        int point1 =0 ;
        int point2 = 0;
        int loc = 0;
        while (point1 < m && point2 < n) {
            if (nums1[point1] <= nums2[point2]) {
                temp[loc] = nums1[point1];
                loc++;
                point1++;
            }else {
                temp[loc] = nums2[point2];
                loc++;
                point2++;
            }
        }
        while (point1 < m) {
            temp[loc++] = nums1[point1++];
        }
        while (point2 < n) {
            temp[loc++] = nums2[point2++];
        }
        nums1 =temp;

        System.out.println(Arrays.toString(nums1));




    }


    /**
     * 深度搜索
     * @param grid
     * @param r
     * @param c
     */
    void dfs(char[][] grid, int r, int c) {
        int nr = grid.length;
        int nc = grid[0].length;

        if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        int num_islands = 0;
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    ++num_islands;
                    dfs(grid, r, c);
                }
            }
        }

        return num_islands;
    }


    /**
     *  无重复字符的最长子串
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
    public String longestPalindrome2(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        String ans = "";
        for (int l = 0; l < n; ++l) {
            for (int i = 0; i + l < n; ++i) {
                int j = i + l;
                if (l == 0) {
                    dp[i][j] = true;
                } else if (l == 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);
                }
                if (dp[i][j] && l + 1 > ans.length()) {
                    ans = s.substring(i, i + l + 1);
                }
            }
        }
        return ans;
    }



    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);



    }

    public int expandAroundCenter(String s,int left,int right){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return right - left - 1;


    }

    public int maxProfit(int[] prices){
        int minPrice = Integer.MAX_VALUE;
        int maxProfite = 0 ;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfite) {
                maxProfite = prices[i] - minPrice;
            }
        }
        return maxProfite;


    }

    public boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);



    }

    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int i = 0, count = 0;
        while (i < flowerbed.length) {
            if (flowerbed[i] == 0
                    && (i == 0 || flowerbed[i - 1] == 0)
                    && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {
                flowerbed[i] = 1;
                count++;
            }
            if (count >= n) {
                return true;
            }
            i++;
        }
        return false;
    }



    public int lastRemaining(int n, int m) {
        int f = 0;
        for (int i = 2; i != n + 1; ++i) {
            f = (m + f) % i;
        }
        return f;
    }
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) {
            return false;
        }
        int revertNumber =0;
        while (x > revertNumber) {
            revertNumber = revertNumber*10+x%10;
            x/=10;
        }
        return x==revertNumber||x==revertNumber/10;

    }


    public void reverseString(char[] s) {
        int n =s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right]= tmp;
        }
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev=null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev =curr;
            curr= nextTemp;
        }
        return prev;

    }

    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return p;

    }


    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) {
                return 0;
            }
            if (rev < Integer.MIN_VALUE / 10 || (rev == Integer.MAX_VALUE / 10 && pop < -8)) {
                return 0;
            }
            rev = rev*10+pop;
        }
        return rev;

    }

    public int climbStairs(int n) {
       int p=0,q=0,r=1;
        for (int i = 1; i <= n; i++) {
            p=q;
            q=r;
            r = p+q;
        }
        return r;
    }



    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

    }






    public int maxSubArray(int[] nums){
        int sum = 0, max = nums[0];
        for (int x : nums) {
            sum = Math.max(sum + x, x);
            max = Math.max(max, sum);
        }
        return max;
    }


    public boolean isValiad(String s) {
        LinkedList<Character> stack = new LinkedList<>();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            if (c == '[') {
                stack.push(']');
            }else if(c=='{'){
                stack.push('}');
            }else if(c=='('){
                stack.push(')');
            }else if(stack.isEmpty()||c!=stack.pop()){
               return false;
            }
        }
        return stack.isEmpty();


    }


    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(nums.length );
        map.put(nums[0], 0);
        int[] result = new int[2];
        for (int i = 1; i < nums.length; i++) {
            int key = target - nums[i];
            if (map.containsKey(key) ){
                result[0]=map.get(key);
                result[1] = i;
                return result;
            }
            map.put(nums[i], i);
        }
        return result;


    }
    public int[] twoSum2(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>(nums.length-1);

        for (int i = 0; i < nums.length; i++) {
            int key= target - nums[i];
            if (map.containsKey(key)) {
                return new int[]{map.get(key),i};
            }
            map.put(nums[i],i );
        }

        return new int[0];


    }




    public String boldWords(String[] words, String s) {
        boolean[] isBold = new boolean[s.length()];
        for (String word : words) {
            int n = s.indexOf(word, 0);
            while (n != -1) {
                for (int i = n; i < n + word.length(); i++) {
                    isBold[i] = true;
                }
                n = s.indexOf(word, n + 1);
            }
        }
        StringBuilder sb = new StringBuilder();
        if (isBold[0]) {
            sb.append("<b>");
        }
        for (int i = 0; i < isBold.length; i++) {
            sb.append(s.charAt(i));
            if (i == isBold.length - 1) {
                if (isBold[i]) {
                    sb.append("</b>");
                }
                break;
            }
            if (isBold[i] && !isBold[i + 1]) {
                sb.append("</b>");
            }
            if (!isBold[i] && isBold[i + 1]) {
                sb.append("<b>");
            }
        }
        return sb.toString();
    }




}
class ListNode {
    int val;
    ListNode next;

    ListNode(){};
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    ListNode(int x){
        val =x;
    }
}

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }

}
